//
// Created by 刘振舟 on 2024/3/18.
//
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <uthash.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

struct Node {
    int val;
    struct Node *left;
    struct Node *right;
    struct Node *next;
};

int maxDepth(struct TreeNode* root){
    if (root == NULL) {
        return 0;
    }
    return fmax(maxDepth(root->left), maxDepth(root->right)) + 1;
}

int maxDiameter = 0;

int getMaxDepthForMaxDiameter(struct TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int leftDepth = getMaxDepthForMaxDiameter(root->left);
    int rightDepth = getMaxDepthForMaxDiameter(root->right);
    maxDiameter = fmax(maxDiameter, leftDepth + rightDepth);
    return fmax(leftDepth, rightDepth) + 1;

}

int diameterOfBinaryTree(struct TreeNode* root){
    maxDiameter = 0;
    getMaxDepthForMaxDiameter(root);
    return maxDiameter;
}


struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL)
        return root;

    struct TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

struct Node* connect(struct Node* root) {
    if (!root) {
        return root;
    }
    int left = 0, right = 0;
    struct Node* queue[5000];
    queue[right++] = root;
    int size = right - left;
    while (size > 0) {
        for (int i = 0; i < size; ++i) {
            struct Node* top = queue[left++];
            if (i < size - 1) {
                top->next = queue[left];
            }

            if (top->left)
                queue[right++] = top->left;
            if (top->right)
                queue[right++] = top->right;
        }
        size = right - left;
    }
    return root;
}


void flatten(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode* cur = root;
    while (cur) {
        if (cur->left) {
            struct TreeNode* next = cur->left;
            struct TreeNode* predecessor = next;
            while (predecessor->right) {
                predecessor = predecessor->right;
            }
            predecessor->right = cur->right;
            cur->right = cur->left;
            cur->left = NULL;
        }
        cur = cur->right;
    }
}

struct TreeNode *construct(int *nums, int low, int high) {
    if (low > high)
        return NULL;
    int maxIndex = low;
    for (int i = low + 1; i <= high; ++i) {
        if (nums[i] > nums[maxIndex])
            maxIndex = i;
    }
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = nums[maxIndex];
    root->left = construct(nums, low, maxIndex - 1);
    root->right = construct(nums, maxIndex + 1, high);
    return root;
}

struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
    return construct(nums, 0, numsSize - 1);
}

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} HashValToIndexMap;

struct TreeNode* createTreeNode(int val) {
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = val;
    root->left = NULL;
    root->right = NULL;
    return root;
}
int getValFromMap(const HashValToIndexMap** obj, int key) {
    HashValToIndexMap *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    if (NULL == pEntry) {
        return -1;
    }
    return pEntry->val;
}

struct TreeNode *buildTreeByPreAndInorder(int *preorder, int preStart, int preEnd, int *inorder, int inStart, int inEnd,
                                          HashValToIndexMap *valToIndexMap) {
    if (preStart > preEnd)
        return NULL;
    int rootVal = preorder[preStart];
    struct TreeNode* root = createTreeNode(rootVal);
    int inorderIndex = getValFromMap(&valToIndexMap, rootVal);
    int leftSize = inorderIndex - inStart;
    root->left = buildTreeByPreAndInorder(preorder, preStart + 1, preStart + leftSize,
                                          inorder, inStart, inorderIndex - 1, valToIndexMap);
    root->right = buildTreeByPreAndInorder(preorder, preStart + leftSize + 1, preEnd,
                                          inorder, inorderIndex + 1,inEnd, valToIndexMap);
    return root;
}


struct TreeNode* buildTreeByPreAndIn(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    HashValToIndexMap* valToIndexMap = NULL, * temp = NULL, * item = NULL;
    for (int i = 0; i < inorderSize; ++i) {
        item = malloc(sizeof(HashValToIndexMap));
        item->key = inorder[i];
        item->val = i;
        HASH_ADD_INT(valToIndexMap, key, item);
    }
    return buildTreeByPreAndInorder(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1, valToIndexMap);
}


struct TreeNode *helper(int *inorder, int inStart, int inEnd, int *postorder, int *postIndex, HashValToIndexMap *map) {
    if (inStart > inEnd) {
        return NULL;
    }
    int value = postorder[(*postIndex)--];
    int index = getValFromMap(&map, value);
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = value;
    root->right = helper(inorder, index + 1, inEnd, postorder, postIndex, map);
    root->left = helper(inorder, inStart, index - 1, postorder, postIndex, map);
    return root;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    HashValToIndexMap* valToIndexMap = NULL, * temp = NULL, * item = NULL;
    for (int i = 0; i < inorderSize; ++i) {
        item = malloc(sizeof(HashValToIndexMap));
        item->key = inorder[i];
        item->val = i;
        HASH_ADD_INT(valToIndexMap, key, item);
    }
    int postorderIndex = postorderSize -1;
    return helper(inorder, 0, inorderSize - 1, postorder, &postorderIndex, valToIndexMap);
}

void hashFree(HashValToIndexMap **obj) {
    HashValToIndexMap *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);
        free(curr);
    }
}

struct TreeNode *createTreeNodeWithLR(int val, struct TreeNode *left, struct TreeNode *right) {
    struct TreeNode *obj = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    obj->val = val;
    obj->left = left;
    obj->right = right;
    return obj;
}


struct TreeNode* dfs(int* preorder, int preLeft, int preRight, int postLeft, int postRight, HashValToIndexMap* map) {
    if (preLeft > preRight) {
        return NULL;
    }
    int leftCount = 0;
    if (preLeft < preRight)
        leftCount = getValFromMap(&map, preorder[preLeft + 1]) - postLeft + 1;

    return createTreeNodeWithLR(preorder[preLeft],
                          dfs(preorder, preLeft + 1, preLeft + leftCount,  postLeft, postLeft + leftCount - 1, map),
                          dfs(preorder, preLeft + leftCount + 1, preRight,  postLeft + leftCount, postRight - 1, map));
}

struct TreeNode* constructFromPrePost(int* preorder, int preorderSize, int* postorder, int postorderSize) {

    HashValToIndexMap* valToIndexMap = NULL, * item = NULL;
    for (int i = 0; i < postorderSize; ++i) {
        item = malloc(sizeof(HashValToIndexMap));
        item->key = postorder[i];
        item->val = i;
        HASH_ADD_INT(valToIndexMap, key, item);
    }

    struct TreeNode* root = dfs(preorder, 0, preorderSize - 1, 0, postorderSize - 1, valToIndexMap);
    hashFree(&valToIndexMap);
    return root;
}



#define MAX_STR_LEN 32

static inline char* tri_hash(int x, int y, int z) {
    char *str = (char *)malloc(sizeof(char) * MAX_STR_LEN);
    sprintf(str, "%d,%d,%d", x, y, z);
    return str;
}

typedef struct {
    char key[MAX_STR_LEN];
    struct TreeNode *node;
    int idx;
    UT_hash_handle hh;
} HashMapItem;

typedef struct {
    void *key;
    UT_hash_handle hh;
} HashSetItem;

int dfs1(struct TreeNode* node, HashMapItem **seen, HashSetItem **repeat, int *idx) {
    if (!node) {
        return 0;
    }
    int ret1 = dfs1(node->left, seen, repeat, idx);
    int ret2 = dfs1(node->right, seen, repeat, idx);
    HashMapItem *pHashMapEntry = NULL;
    char *hashKey = tri_hash(node->val, ret1, ret2);
    HASH_FIND_STR(*seen, hashKey, pHashMapEntry);
    if (pHashMapEntry) {
        HashSetItem *pHashSetEntry = NULL;
        HASH_FIND_PTR(*repeat, &(pHashMapEntry->node), pHashSetEntry);
        if (pHashSetEntry == NULL) {
            pHashSetEntry = (HashSetItem *)malloc(sizeof(HashSetItem));
            pHashSetEntry->key = (void *)pHashMapEntry->node;
            HASH_ADD_PTR(*repeat, key, pHashSetEntry);
        }
        free(hashKey);
        return pHashMapEntry->idx;
    } else {
        pHashMapEntry = (HashMapItem *)malloc(sizeof(HashMapItem));
        strcpy(pHashMapEntry->key, hashKey);
        pHashMapEntry->node = node;
        pHashMapEntry->idx = ++(*idx);
        HASH_ADD_STR(*seen, key, pHashMapEntry);
        free(hashKey);
        return *idx;
    }
}

struct TreeNode** findDuplicateSubtrees(struct TreeNode* root, int* returnSize){
    HashMapItem *seen = NULL;
    HashSetItem *repeat = NULL;
    int idx = 0;
    dfs1(root, &seen, &repeat, &idx);

    int count = HASH_COUNT(repeat), pos = 0;
    struct TreeNode** ret = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * count);
    HashSetItem *cur, *tmp;
    HASH_ITER(hh, repeat, cur, tmp) {
        ret[pos++] = (struct TreeNode*)cur->key;
        HASH_DEL(repeat, cur);
        free(cur);
    }
    *returnSize = count;
    HashMapItem *curMap, *tmpMap;
    HASH_ITER(hh, seen, curMap, tmpMap) {
        HASH_DEL(seen, curMap);
        free(curMap);
    }
    return ret;
}


void helperSerialize(struct TreeNode *root, char *result) {
    if (root == NULL) {
        strcat(result, "null,");
    } else {
        char tempBuffer[7] = {0};
        sprintf(tempBuffer, "%d,", root->val);
        strcat(result, tempBuffer);
        helperSerialize(root->left, result);
        helperSerialize(root->right, result);
    }
}

/** Encodes a tree to a single string. */
char* serialize(struct TreeNode* root) {
    if (root == NULL)
        return "null";
    char *result = malloc(80000 * sizeof(char));
    memset(result, 0, 80000 * sizeof(char));
    helperSerialize(root, result);
    return result;
}

struct TreeNode *helperDeserialize(char *data) {
    /*在 strtok 函数中，当你第一次调用它时，你需要提供一个待分解的字符串 str 和一个分隔符 delim。
     * 函数会返回该字符串中的第一个标记（token），并内部保存一个指针，指向下一个标记。
    当你希望继续分解相同的字符串时，你应该将 str 参数设置为 NULL，
     这会告诉 strtok 函数使用之前保存的内部指针继续分解相同的字符串。*/
    char *tempChar = strtok(data, ",");
    if (!strcmp(tempChar, "null"))
        return NULL;
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = atoi(tempChar);
    root->left = helperDeserialize(NULL);
    root->right = helperDeserialize(NULL);
    return root;
}

/** Decodes your encoded data to tree. */
struct TreeNode* deserialize(char* data) {
    if (!strcmp(data, "null")) {
        return NULL;
    }
    return helperDeserialize(data);
}

// Your functions will be called as such:
// char* data = serialize(root);
// deserialize(data);



int main() {
    struct TreeNode* root = malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->right = malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right->left = malloc(sizeof(struct TreeNode));
    root->right->left->val = 4;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right = malloc(sizeof(struct TreeNode));
    root->right->right->val = 5;
    root->right->right->left = NULL;
    root->right->right->right = NULL;
    char* res = serialize(root);
    printf("%s", res);
    struct TreeNode* node = deserialize(res);
    return 0;
}